package Aula7;

import java.util.ArrayList;

public class TopologicoImpl implements Topologico {

	private boolean[][] matrizGrafo;
	private ArrayList<Integer> excluidos;

	public TopologicoImpl() {
		super();
		excluidos = new ArrayList<Integer>();
	}

	private int numeroDeEntradas(boolean[][] matrizGrafo, int vertice) {
		if (matrizGrafo == null) {
			throw new RuntimeException("Grafo nao preenchido!");
		}
		int cont = 0;
		for (int linha = 0; linha < matrizGrafo.length; linha++) {
			/*
			 * Vertice nao precisa verificar, pois se ele ja foi excluido esse
			 * metodo nao sera usado com ele.
			 */
			if (excluidos.contains(linha)) {
				continue;
			}
			if (matrizGrafo[linha][vertice]) {
				cont++;
			}
		}
		return cont;
	}

	private ArrayList<Integer> verticesZeroEntradas() {
		ArrayList<Integer> lista = new ArrayList<Integer>();
		for (int vertice = 0; vertice < matrizGrafo.length; vertice++) {
			if (excluidos.contains(vertice)) {
				continue;
			}
			if (numeroDeEntradas(matrizGrafo, vertice) == 0) {
				lista.add(vertice);
			}
		}
		/* Isso nunca vai acontecer! Pois o grafo sempre vai ser aciclico */
		if (lista.size() == 0)
			throw new RuntimeException("Grafo ciclico ou ha ciclos!");

		return lista;
	}

	public boolean ehOrdemDeterministica() {
		excluidos = new ArrayList<Integer>();
		for (int i = 0; i < matrizGrafo.length; i++) {
			ArrayList<Integer> lista = verticesZeroEntradas();
			if (lista.size() > 1) {
				return false;
			} else {
				excluidos.add(lista.get(0));
			}
		}
		return true;
	}

	public String mostrarOrdemTopologica() {
		excluidos = new ArrayList<Integer>();

		int verticeZero = verticesZeroEntradas().get(0);
		excluidos.add(verticeZero);

		String resposta = "" + verticeZero;

		for (int i = 1; i < matrizGrafo.length; i++) {
			verticeZero = verticesZeroEntradas().get(0);
			excluidos.add(verticeZero);
			resposta += " " + verticeZero;
		}
		return resposta;
	}

	public void preencherGrafo(boolean[][] matrizGrafo, int tamanho) {
		this.matrizGrafo = matrizGrafo;
	}

	public static void main(String[] args) {
		Topologico t = new TopologicoImpl();

		boolean[][] matriz = { { false, true, true }, { false, false, false },
				{ false, false, false } };
		int tamanhoMatriz = 3;

		t.preencherGrafo(matriz, tamanhoMatriz);
		System.out.println("A matriz tem apenas uma ordenacao?: "
				+ t.ehOrdemDeterministica());

		System.out.println("Uma ordem possivel: " + t.mostrarOrdemTopologica());

	}

}
